package everyday;

import org.junit.jupiter.api.Test;
import tool.s;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-05-31-10:18
 * @Description: 1.0
 */
public class T1130 {
    int[][] max;
    int[][] sum;
    final int Max=Integer.MAX_VALUE;

    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        max = new int[n][n];
        sum = new int[n][n];
        for (int i = 0; i < n; i++) {
            max[i][i] = arr[i];
            Arrays.fill(sum[i], Max);
            sum[i][i] = 0;
        }
        dp(0,n-1);
        return sum[0][n - 1];
    }

    public int[] dp(int l, int r) {
        if (sum[l][r] != Max) return new int[]{sum[l][r], max[l][r]};
        for (int i = l; i < r; i++) {
            int[] left = dp(l, i);
            int[] right = dp(i + 1, r);
            max[l][r] = Math.max(left[1], right[1]);
            sum[l][r] = Math.min(sum[l][r], left[0] + right[0] + left[1] * right[1]);
        }
        return new int[]{sum[l][r],max[l][r]};
    }

    @Test
    public void test() {
        System.out.println(mctFromLeafValues(new int[]{15, 13, 5, 3, 15}));
    }
}
